The present invention relates to multiplex communication systems for transferring information in packets and more particularly, to scheduling and header compression of packets in a multilayered network architecture.
Modern communications networks carry increasing amounts of packet traffic which is associated with real-time voice, video, and related data. The Internet, for example, is seeing many new applications which take advantage of what is a relatively less costly alternative to conventional telephone call connections for sending a variety of data including real time voice and video. Trends toward real time applications over the Internet are driven in part by increasingly powerful computers being installed in private homes and the proliferation of the Internet as a focal point for various on-line activities such as holding voice conversations, listening to music, watching video clips, and the like. Unlike Internet communications which occur between computers on high bandwidth commercial connections, bandwidth in a typical home is limited by connectivity constraints imposed by modem speed, line quality, and the like.
Further compounding the basic problem of limited bandwidth, is the limitation on the amount of actual information transmitted as a result of packet overhead due to protocol headers. Basic Internet protocols were developed primarily for making sure that packets were delivered accurately end to end at a time when little consideration was paid to real time issues.
Three layer interface architectures including protocols such as X.25, for example, were developed for controlling transfer at the lower levels while higher layer protocols were developed to control more sophisticated functions (see, xe2x80x9cOpen Systems Interconnect (OSI)xe2x80x94New International Standards Architectures and Protocols for Distributed Information Systems,xe2x80x9d special issue, Proceedings of the IEEE, H. C. Folts and R. des Jardins, eds., vol. 71, no. 12, December 1983). According to the design philosophy, lower layer functions were contemplated to be xe2x80x9ctransparentxe2x80x9d to higher layer functionality and thus much of what can be accomplished at the lower layers is limited only by the ability of lower layer hardware and software to preserve that transparency. At the lowest layer, the Physical Layer, a protocol specification governs the physical connection between devices, such as, for example, the X.21 protocol. Next, the Data Link Layer specifies the protocol for, for example, accepting packets from higher layers and placing them into, for example, HDLC frames for transfer across the Physical Layer. The Data Link layer further may accept framed information from the Physical Layer and unpack it for transfer up to the Network Layer. At the Network Layer, or packet layer, multiple logical connections may be established and addresses attached to packets based on several assumptions including that successful end to end delivery is not guaranteed, that orderly delivery is not guaranteed, and that packets or xe2x80x9cdatagramsxe2x80x9d are delivered one at a time each containing information such as destination address, and the like.
It is important to note that while various lower layers are discussed herein, datagrams from higher layers may form the input to a Network Layer process or system, which in turn provide input to successively lower layers, and eventually to the destination. Higher layer datagrams input to a Network Layer entity may be input from, for example, a Transport Layer process or system. A typical and well know transport layer protocol is the Transport Control Protocol (TCP) although other Transport Layer protocols are known and used. In particular, the User Datagram Protocol (UDP) may often be used as a Transport Layer protocol. UDP is a protocol which defines a connectionless datagram service. A Transport Layer process or system implementing UDP may produce self-contained data packets which include destination routing information.
A ubiquitous protocol for Network Layer communications over the Internet is the Internet Protocol (IP). The IP specification includes an enumeration of fields associated with the IP header which fields contain information about an associated packet including information for determining how the packet should be delivered. The IP header fields will be described in greater detail herein below. For a more complete understanding of the contents of the IP header, see xe2x80x9cInternet Protocol Specificationxe2x80x9d, E. J. Postel, SRI International, Menlo Park, Calif., September 1981, RFC791.
For Data Link Layer communications, Point-to-Point-Protocol (PPP) has become a dominant protocol. PPP includes three main components: a method of encapsulating multi-protocol datagrams, a datagram being a unit of transmission in the network layer (such as IP), a link control protocol (LCP) for establishing, configuring and testing the data-link connection, and a family of network control protocols (NCP) for establishing and configuring different network-layer protocols.
PPP is designed to transport packets between two so-called peers, i.e. the two ends of a link conforming to the protocol. Accordingly, the LCP may be used to agree upon the encapsulation format options, handle varying limits on sizes of packets, detect configuration errors, and terminate the link. Other optional facilities are the authentication of the identity of its peer on the link, and the determination when a link is functioning properly and when it is failing. PPP links-provide full-duplex simultaneous bidirectional operation. A definition of PPP may be found in the Networking Group Request for Comments RFC 1661, xe2x80x9cThe Point to Point Protocolxe2x80x9d editor W. Simpson, July 1994.
Communication across a link established using PPP is accomplished such that a datagram associated with a protocol may be encapsulated into one or more frames. A frame, as described above, may include a header and/or a trailer, along with some number of units of data. However, it is conventional that an entire packet is mapped into a frame. Conventional framing breaks down however during conditions of heavy network congestion where fragmentation methods may be used to improve flow control management. Such congestion has arisen due to, among other factors, the increase in traffic caused by increased numbers of greater bandwidth connections provided by, for example, multilink service. Since both basic and primary rate ISDN, for example, allow for multiple simultaneous channels between systems to allow for bandwidth on demand, problems associated with such services must be addressed. Congestion giving rise to latency may be a particular problem for real time data such as voice or video, VoIP, Telnet, and the like. Such real time data formats have little or no tolerance to packet latency, jitter, packet reordering and related problems. Problems associated with the multilink environment only amplify the unique real time packet data requirements.
To ease congestion in the multilink environment, one solution known as Link Fragmentation and Interleaving (LFI) is proposed in the White Paper entitled xe2x80x9cCisco IOS(trademark) Software Quality of Service Solutionsxe2x80x9d, Apr. 8, 1999, by Cisco Systems. In LFI, delay and jitter are reduced by breaking up large datagrams and interleaving time sensitive packets with the resulting packet fragments. LFI is contemplated for relatively low speed links where serialization delay is the predominant delay factor. LFI simply requires that PPP be configured to allow for interleaving. Otherwise, LFI is transparent to PPP.
A similar solution is proposed in Internet Engineering Task Force (IETF), INTERNET-DRAFT, xe2x80x9cMulti-Class Extension to Multi-Link PPPxe2x80x9d, June 1999, expires: December 1999, by Carsten Borman. Here, a fragment oriented solution may be found for the real time encapsulation of format which is part of the standard architecture of, for example, integrated services communications links.
Certain problems associated with conventional LFI, multi-link PPP, and related data transfer may best be illustrated by an example. The transfer of a 1.5 kbyte packet on a 28.8 kbit/s modem link may occupy the link, making it unavailable for data transfer of packets associated with other links in the multi-link environment, for upwards of 400 ms. Such delay may create round trip delays associated with interactive real time data, such as a voice conversation, of close to a second. By fragmenting packets of various priorities larger than a predetermined size high priority packets or fragments thereof may be sent between fragments of lower priority packets. Existing multi-link PPP specifications already provide for fragmentation by providing sequence numbers and begin and end bits in the PPP encapsulation format. However, existing multi-link PPP does not provide for the suspension of transfer of fragments of one packet in order to send another, due to contiguous packet numbering schemes. The solution proposed by Borman, supra, includes running multiple multi-link protocol instances on the same link allowing for nesting of multiple suspendable classes using unused bits in the multi-link PPP protocol to specify class numbers. Accordingly, fragments belonging to a particular class can be sent without the multi-link header and four to twelve levels of suspension may be achieved depending on the number of header bits.
Regardless of the methods of scheduling fragments contemplated, problems arise in implementation. In particular, it should be noted that the lower three protocol layers and associated protocols including, for example, UDP, IP, and PPP, along with the physical layer typically reside on hardware resources, such as routers, which may introduce limitations that are detrimental to the benefits gained from fragmentation and other scheduling methods. In particular, a router, for example, may typically queue outbound packets together in the same transmit queue once priority or the like has been established. The configuration of a typical outbound packet queue is generally First In First Out (FIFO) and has a level of intrinsic delay associated with the queue depth. Further, a router experiencing high traffic levels and using a typical outbound packet queue raises the possibility of packet dropping when congestion occurs, even when using LFI, multi-link PPP or the like. If packets are forced to be dropped from downstream queues after IP scheduling occurs, problems related to packets received out of sequence may occur. Depending on the link configuration, request for retransmission of the missing packets, for example, may cause delay and degradation of real time data.
Packet dropping can be particularly troublesome when used in conjunction with other methods of reducing congestion such as, for example, header compression. By compressing or discarding certain portions of information contained in a typical header, header compression methods reduce the overall size of the datagram or packet. This is particularly important in the case of small packets typically used for real time data transfer applications where the header may represent close to 100% packet overhead. Although, header compression may be performed at various stages, problems arise due to an assumption which must be made in the art when using header compression that packet reordering or resequencing, including the effects of packet dropping, will not occur. Approaches for dealing with this problem adds nearly as much header overhead as was saved originally with header compression techniques. For more general information on header compression see Internet Engineering Task Force (IETF), INTERNET-DRAFT, xe2x80x9cProviding Integrated Services Over Low-bitrate Linksxe2x80x9d, June 1999, expires: December 1999, by Carsten Borman, and see also Networking Group Request for Comments RFC 1144, xe2x80x9cCompressing TCP/IP Headers for Low-Speed Serial Linksxe2x80x9d, editor V. Jacobson, February 1990.
On slow links, as described, time sensitive packets can not afford to wait for the completion of, for example a long Best Efforts (BE) data packet. Using IP fragmentation may improve latency for such packets, but at a cost of adding a header of around 20 bytes for each segment. Another solution is to use Multi-link PPP segmentation that adds a header of 2 or 4 bytes to each segment. Such headers are designed to propagate scheduling information to the segments or fragments. Header compression, however, makes IP scheduling difficult. When header compression is used, information including the identification field in the IP header becomes unavailable to lower layers after compression. If a HC packet is dropped, the resulting missing sequence number at the receiver will cause problems on the link, as previously described, since the receiver will, for example, request retransmission of the dropped packet and the layer responsible will be unable to identify which packet was dropped and will thus be unable to request the dropped packet from higher layers, introducing further delay and degradation of quality.
Therefore, it would be appreciated in the art for a method and apparatus which handles scheduling and reduces the adverse effects on scheduling imposed by header compression on dropped packets. Such a method and apparatus would operate without disruption of the operation of the IP layer allowing generic IP scheduling on pure IP packets with header compression.
It is therefore an object of the present invention to provide a method and apparatus for reducing packet delay using scheduling and header compression.
It is a further object of the present invention to provide such a method and apparatus at various layers within a multi-layer protocol implementation.
Therefore, in accordance with one aspect of the present invention, the foregoing and other objects are achieved in a method and apparatus for reducing delay in the transmission of a plurality of packets. The packets may have a plurality of classifications according to a multi-layer protocol having at least a higher layer, and a lower layer. Packets may be scheduled according the associated classifications. If congestion occurs during scheduling, packets which cannot be scheduled may be discarded. After scheduling and discarding some packet headers may be compressed and, accordingly, sequence information may be preserved.
In accordance with another embodiment of the present invention, packets may be queued in a first and a second queue, after scheduling, discarding, and compressing, according to at least two of the plurality of classifications, the first queue having priority over the second queue. For example, one the two possible classifications may include Best Efforts classification such that queuing would include determining whether packets are classified as Best Efforts packet and if so, queuing Best Efforts packets into, for example, the second queue.
It should be understood that a number of classifications may be included which may be associated with, for example, QoS levels as may be found in an IP header associated with a packet. Classifications may also be associated with a plurality of delay factors and it may be preferable to establish a plurality of queues based on the plurality of classifications. Accordingly, each packet may be queued into one of the plurality of queues based on an associated classification.
In accordance with yet another embodiment of the present invention, the plurality of classification may be associated with Link Fragmentation and Interleaving (LFI) as described herein above. Alternatively, the plurality of classifications may be associated with Multilink PPP as also described herein above.
It should further be noted that in accordance with the present invention, scheduling may be performed at the higher or lower layers, wherein the lower layer may include a PPP layer as described above. The lower layer may further include an HDLC layer and when scheduling is performed therein, a tag may be created for each of the packets prior to header compression. The tag may be added thereafter and may be removed prior to transmitting. Each packet from the first and the second queue may be queued in an outbound packet queue having a queue depth of no greater than one.